SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Cyrus–Beck algorithm</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Cyrus–Beck algorithm</span></span>

</h1>

</header>

<p>In <a href="Computer_graphics" title="Computer graphics">computer graphics</a>, the <b>Cyrus–Beck algorithm</b> is a generalized <a href="Algorithm" title="Algorithm">algorithm</a> for <a href="Line_clipping" title="Line clipping">line clipping</a>. It was designed to be more efficient than the <a href="Cohen%E2%80%93Sutherland_algorithm" title="Cohen–Sutherland algorithm">Cohen–Sutherland algorithm</a>, which uses repetitive clipping.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Cyrus–Beck is a general algorithm and can be used with a <a href="Convex_polygon" title="Convex polygon">convex polygon</a> clipping window, unlike Cohen-Sutherland, which can be used only on a rectangular clipping area.

</p><p>Here the <a href="Parametric_equation" title="Parametric equation">parametric equation</a> of a line in the view plane is

</mrow>

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {p} (t)=t\mathbf {p} _{1}+(1-t)\mathbf {p} _{0}}</annotation>

</semantics>

</math></span></span>

where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\leq t\leq 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\leq t\leq 1}</annotation>

</semantics>

</math></span><img src="./86496f1001838495964ccca2851a6f29ff0c36a9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:9.361ex; height:2.343ex;" alt="{\displaystyle 0\leq t\leq 1}" loading="lazy"></span>.

</p><p>Now to find the intersection point with the clipping window, we calculate the value of the <a href="Dot_product" title="Dot product">dot product</a>. Let <span class="nowrap">⁠<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {p} _{E}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {p} _{E}}</annotation>

</semantics>

</math></span><img src="./8c7a249772094266a60a037eddc3ab183532bd45.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.973ex; height:2.176ex;" alt="{\displaystyle \mathbf {p} _{E}}" loading="lazy"></span>⁠</span> be a point on the clipping plane <span class="nowrap">⁠<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E}</annotation>

</semantics>

</math></span><img src="./4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy"></span>⁠</span>.

</p><p>Calculate <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {n} \cdot (\mathbf {p} (t)-\mathbf {p} _{E})}">

</mrow>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {n} \cdot (\mathbf {p} (t)-\mathbf {p} _{E})}</annotation>

</semantics>

</math></span><img src="./e460795b152ab74b19dd0c01bd300a9ab4627712.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.921ex; height:2.843ex;" alt="{\displaystyle \mathbf {n} \cdot (\mathbf {p} (t)-\mathbf {p} _{E})}" loading="lazy"></span>:

</p>

<li>if = 0, vector pointed parallel to plane containing <span class="nowrap">⁠<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math></span><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"></span>⁠</span>;</li>

<li>if > 0, vector pointed away from interior.</li></ul>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathbf {n}}}</annotation>

</semantics>

</math></span><img src="./8be8da0254fd38956b8a83d20286825bf64bf7fb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.485ex; height:1.676ex;" alt="{\displaystyle {\mathbf {n}}}" loading="lazy"></span>⁠</span> stands for <a href="Normal_(geometry)" title="Normal (geometry)">normal</a> of the current clipping plane (pointed away from interior).

</p><p>By this we select the point of intersection of line and clipping window where (dot product is 0) and hence clip the line.

</p>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="https://www.slideshare.net/johanna20/clipping-presentation">"Clipping" (presentation)</a>.</span>

</li>

</ol></div></div>

<p>Algorithms used for the same purpose:

</p>

<ul><li><a href="Cohen%E2%80%93Sutherland_algorithm" title="Cohen–Sutherland algorithm">Cohen–Sutherland algorithm</a></li>

<li><a href="Liang%E2%80%93Barsky_algorithm" title="Liang–Barsky algorithm">Liang–Barsky algorithm</a></li>

<li><a href="Nicholl%E2%80%93Lee%E2%80%93Nicholl_algorithm" title="Nicholl–Lee–Nicholl algorithm">Nicholl–Lee–Nicholl algorithm</a></li>

<li><a href="Fast_clipping" class="mw-redirect" title="Fast clipping">Fast clipping</a></li></ul>

<p>References in other media:

</p>

<ul><li><i><a href="Tron%3A_Uprising" title="Tron: Uprising">Tron: Uprising</a></i></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li>Mike Cyrus, Jay Beck. "<a rel="nofollow" class="external text" href="https://www.sciencedirect.com/science/article/pii/0097849378900213">Generalized two- and three-dimensional clipping</a>". Computers & Graphics, 1978: 23–28.</li>

<li>James D. Foley. <i><a rel="nofollow" class="external text" href="https://books.google.com/books?id=-4ngT05gmAQC">Computer graphics: principles and practice</a></i>. Addison-Wesley Professional, 1996. p. 117.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external free" href="https://web.archive.org/web/20101203041134/http://cs1.bradley.edu/public/jcm/cs535CyrusBeck.html">https://web.archive.org/web/20101203041134/http://cs1.bradley.edu/public/jcm/cs535CyrusBeck.html</a></li>

<li><a rel="nofollow" class="external free" href="https://web.archive.org/web/20110725233122/http://softsurfer.com/Archive/algorithm_0111/algorithm_0111.htm">https://web.archive.org/web/20110725233122/http://softsurfer.com/Archive/algorithm_0111/algorithm_0111.htm</a></li></ul>

<p><br>

</p>

/* start https://en.wikipedia.org/ */

.mw-parser-output .asbox{position:relative;overflow:hidden}.mw-parser-output .asbox table{background:transparent}.mw-parser-output .asbox p{margin:0}.mw-parser-output .asbox p+p{margin-top:0.25em}.mw-parser-output .asbox-body{font-style:italic}.mw-parser-output .asbox-note{font-size:smaller}.mw-parser-output .asbox .navbar{position:absolute;top:-0.75em;right:1em;display:none}.mw-parser-output :not(p):not(.asbox)+style+.asbox,.mw-parser-output :not(p):not(.asbox)+link+.asbox{margin-top:3em}

/* end https://en.wikipedia.org/ */

</style></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-06-01" href="https://en.wikipedia.org/wiki/?title=Cyrus%E2%80%93Beck_algorithm&oldid=1226716332">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>